package 二叉树;

import java.util.ArrayList;

public class 二叉树的递归遍历 {
    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //前序遍历
    class Solution{
        ArrayList<Integer> preOrderReverse(TreeNode root){
            ArrayList<Integer> result = new ArrayList<>();
            preOrder(root,result);
            return result;
        }
    }

    private void preOrder(TreeNode root, ArrayList<Integer> result) {

        if (root==null){
            return;
        }

        result.add(root.val);
        preOrder(root.left,result);
        preOrder(root.right,result);

    }



    //中序遍历
    class Solution2{
        ArrayList<Integer> inOrderReverse(TreeNode root){
            ArrayList<Integer> res = new ArrayList<>();
            inOrder(root,res);
            return res;
        }


    }

    private void inOrder(TreeNode root, ArrayList<Integer> list) {
        if (root==null)
            return;
        inOrder(root.left,list);
        list.add(root.val);
        inOrder(root.right, list);
    }





    //后序遍历
    class Solution3{
        ArrayList<Integer> postOrderReverse(TreeNode root){
            ArrayList<Integer> res = new ArrayList<>();
            postOrder(root,res);
            return res;
        }


    }

    private void postOrder(TreeNode root, ArrayList<Integer> list) {
        if (root==null)
            return;
        inOrder(root.left,list);
        inOrder(root.right, list);
        list.add(root.val);
    }
}
